Computational Game Theory

\[ \newcommand{\IR}{\mathbb{R}} \newcommand{\IRnn}{\IR_{\geq 0}} \newcommand{\IRp}{\IR_{\gt 0}} \newcommand{\coloneqq}{:=} \newcommand{\eqqcolon}{=:} \newcommand{\dcup}{\mathbin{\dot\cup}} \newcommand{\sMid}{\,|\,} \newcommand{\SMid}{\middle|} \newcommand{\abs}[1]{\lvert#1\rvert} \newcommand{\Abs}[1]{\left\lvert#1\right\rvert} \newcommand{\norm}[1]{\lVert#1\rVert} \newcommand{\Norm}[1]{\left\lVert#1\right\rVert} \newcommand{\PSet}[1]{2^{#1}} \newcommand{\transp}{^\top} \newcommand{\eps}{\varepsilon} \newcommand{\next}{\mathop{\mathrm{next}}} \newcommand{\prev}{\mathop{\mathrm{prev}}} \newcommand{\classP}{\mathrm{P}} \newcommand{\classNP}{\mathrm{NP}} \newcommand{\classNPC}{\mathrm{NPC}} \newcommand{\classFP}{\mathrm{FP}} \newcommand{\classFNP}{\mathrm{FNP}} \newcommand{\classFNPC}{\mathrm{FNPC}} \newcommand{\classTFNP}{\mathrm{TFNP}} \newcommand{\classPPAD}{\mathrm{PPAD}} \newcommand{\SAT}{\style{font-variant-caps:small-caps}{\text{Sat}\,}} \newcommand{\NASH}{\style{font-variant-caps:small-caps}{\text{Nash}\,}} \newcommand{\FSAT}{\style{font-variant-caps:small-caps}{\text{FSat}\,}} \newcommand{\FNASH}{\style{font-variant-caps:small-caps}{\text{FNash}\,}} \newcommand{\SPERNER}{\style{font-variant-caps:small-caps}{\text{Sperner}\,\,}} \newcommand{\epsBROUWER}{\eps\style{font-variant-caps:small-caps}{\text{Brouwer}\,\,\,}} \newcommand{\TRUE}{\style{font-variant-caps:small-caps}{\text{True}\,}} \newcommand{\FALSE}{\style{font-variant-caps:small-caps}{\text{False}\,}} \]

§2.4 Some Complexity Theory

$\Pi, \Pi'$ two decision problems

$\Pi \in \classP$ (deterministic polynomial time) if $\exists$ polynomial algorithm $\mathcal{A}: \Pi \to \set{\text{Yes},\text{No}}$
(i.e., $\exists$ polynomial $p$: $\forall I \in \Pi: \mathrm{runtime}(\mathcal{A}(I)) \leq p(\abs{I})$)
$\Pi \in \classNP$ (non-deterministic polynomial time) if $\exists$ polynomial certificates for Yes-instances
(i.e., $\forall I \in \Pi$ Yes-instance $\exists$ polynomial-time verifiable proof for being Yes-instance)
$\Pi' \leq \Pi$ ($\Pi'$ reducable to $\Pi$) if $\exists f: \Pi' \to \Pi$ s.th. for every $I \in \Pi'$:
- $f(I)$ can be constructed in polynomial time in $\abs{I}$
- $f(I)$ Yes-instance of $\Pi \iff I$ Yes-instance of $\Pi'$
$\Pi \in \classNPC$ (NP-complete) if $\Pi \in \classNP$ and $\forall \Pi' \in \classNP: \Pi' \leq \Pi$

Observations:

$\classP \subseteq \classNP$
$\Pi' \leq \Pi$ and $\Pi \in \classP \implies \Pi' \in \classP$
$\classP \neq \classNP \implies \forall \Pi \in \classNPC: \Pi \notin \classP$
$\Pi \in \classNPC \iff \Pi \in \classNP$ and $\exists \Pi' \in \classNPC: \Pi' \leq \Pi$

Satisfiability ($\SAT$):
Input: boolean formula in in CNF (i.e. $m$ clauses $C_1, \dots, C_m$ in $n$ variables $x_1, \dots, x_n$)
Question: $\exists$ satisfying interpretation? (i.e., $\beta: \set{x_1,\dots,x_n} \to \set{\TRUE,\FALSE}$ satisfying all $C_i$)

Fact (Cook-Levin): $\SAT$ is NP-complete

Nash ($\NASH$):
Input: finite $2$ player game $G$
Question: $\exists$ MNE of $G$?

#Nash $\geq 2$ ($\NASH+_1$):
Input: finite $2$ player game $G$
Question: Are there at least two different MNE in $G$?

Thm 2.18 (Conitzer, Sandholm): $\NASH+_1$ is NP-complete

Transformation $f: \SAT \to \NASH+_1$:
instance $I \in \SAT$ with variable set $V$, literal set $L \coloneqq \set{\pm v \sMid v \in V}$,
instance $↧$ mmmm clause set $C \subseteq \PSet{L}$ and $n \coloneqq \abs{V}$
instance $f(I) \in \NASH+_1$: symmetric 2-player game $G=([2], S,u)$:

$S_1 \coloneqq S_2 \coloneqq V \dcup L \dcup C \dcup \set{\bot}$
$u_1(v,\ell) \coloneqq \begin{cases}{\color{var(--NRcol0)}0}, & \ell \in \set{\pm v} \\ {\color{var(--NRcoln)}n}, &\text{else}\end{cases}$ f.a. $v \in V, \ell \in L$
$u_1(\ell',\ell) \coloneqq \begin{cases}{\color{var(--NRcolnm4)}n-4}, & \ell' = -\ell \\ {\color{var(--NRcolnm1)}n-1}, &\text{else}\end{cases}$ f.a. $\ell', \ell \in L$
$u_1(c,\ell) \coloneqq \begin{cases}{\color{var(--NRcol0)}0}, & \ell \in c \\ {\color{var(--NRcoln)}n}, &\text{else}\end{cases}$ f.a. $c \in C, \ell \in L$
$u_1(s,s') \coloneqq {\color{var(--NRcol0)}{\color{var(--NRcolnm1)}n-1}}$ f.a. $s \in V \cup L \cup C, s' \in V \cup C$
$u_1(s,\bot) \coloneqq {\color{var(--NRcol0)}0}$, $u_1(\bot,s) \coloneqq {\color{var(--NRcolnm1)}n-1}$ f.a. $s \in V \cup L \cup C$
$u_1(\bot,\bot) \coloneqq {\color{var(--NRcoleps)}\eps} \in \IRp$

Example:

$(x_1 \lor \bar x_2) \land (\bar x_1 \lor x_2)$
$↧$

$u_1/u_2$	$V$		$L$				$C$
	$x_1$	$x_2$	$+x_1$	$-x_1$	$+x_2$	$-x_2$	$x_1 \lor \bar x_2$	$\bar x_1 \lor x_2$	$\bot$
$x_1$	$n-4$	$n-4$	$0$	$0$	$n$	$n$	$n-4$	$n-4$	$0$
$x_2$	$n-4$	$n-4$	$n$	$n$	$0$	$0$	$n-4$	$n-4$	$0$
$+x_1$	$n-4$	$n-4$	$n-1$	$n-4$	$n-1$	$n-1$	$n-4$	$n-4$	$0$
$-x_1$	$n-4$	$n-4$	$n-4$	$n-1$	$n-1$	$n-1$	$n-4$	$n-4$	$0$
$+x_2$	$n-4$	$n-4$	$n-1$	$n-1$	$n-1$	$n-4$	$n-4$	$n-4$	$0$
$-x_2$	$n-4$	$n-4$	$n-1$	$n-1$	$n-4$	$n-1$	$n-4$	$n-4$	$0$
$x_1\lor \bar x_2$	$n-4$	$n-4$	$0$	$n$	$n$	$0$	$n-4$	$n-4$	$0$
$\bar x_1\lor x_2$	$n-4$	$n-4$	$n$	$0$	$0$	$n$	$n-4$	$n-4$	$0$
$\bot$	$n-1$	$n-1$	$n-1$	$n-1$	$n-1$	$n-1$	$n-1$	$n-1$	$\eps$

Search Problems

$\Pi, \Pi'$ two search problems (i.e., for instane $I \in \Pi$ find solution $x$ of $I$ or say "no" if no solution exists)

$\Pi \in \classFP$ if $\exists$ polynomial algorithm $\mathcal{A}: \Pi \to \set{\text{solutions}} \cup \set{\text{"no"}}$
$\Pi \in \classFNP$ if every instance with a solution has polynomial-sized solution
$\Pi \in \classFNP$ and correctness of a solution can be verified in polynomial time
$\Pi' \leq \Pi$ if $\exists$ polynomial time computable transformations $f$ and $g$ s.th.:
- $I \in \Pi'$ has solution $\implies f(I) \in \Pi$ has solution
- $g(x)$ solution for $I \in \Pi' \impliedby x$ solution for $f(I) \in \Pi$
$\Pi \in \classFNPC$ (FNP-complete) if $\Pi \in \classFNP$ and $\forall \Pi' \in \classFNP: \Pi' \leq \Pi$
$\Pi \in \classTFNP$ (total search problem) if $\Pi \in \classFNP$ and every instance of $\Pi$ has a solution
$\Pi \in \classPPAD$ (polynomial parity argument, direted case) if $\Pi \in \classFNP$ and f.a. $I \in \Pi$:
- $\exists$ set $S_I$ containing all polynomail-sized solutions of $I$ and a special element $0$
- $\exists$ polynomial algorithms $\next_I, \prev_I: S_I \to S_I \dcup \set{\bot}$ s.th.:
  - $\forall x,y \in S_I: x = \prev_I(y) \iff \next_I(x) = y$
  - $\prev_I(0) = \bot$ and $\next_I(0) \neq \bot$
  - $\forall x \in S_I \setminus \set{0}: x$ solution for $I \iff \prev_I(x) = \bot \mathbin{\dot{\lor}} \next_I(x) = \bot$
$\Pi$ PPAD-complete if $\Pi \in \classPPAD$ and $\forall \Pi' \in \classPPAD: \Pi' \leq \Pi$

$\FNASH$: Input: finite 2-player game $G$
$\FNASH$: Output: mixed Nash equilibrium of $G$

Observation: $\FNASH \in \classTFNP$

"Observation": $\FNASH \in \classPPAD$

Fact 2.25: $\FNASH$ is PPAD-complete

$\FSAT$: Input: boolean formula $\phi$ in in CNF
$\FSAT$: Output: satisfying interpretation for $\phi$

Fact 2.21: $\FSAT$ is FNP-complete

Observations:

$\classFP \subseteq \classFNP$
$\Pi' \leq \Pi$ and $\Pi \in \classFP \implies \Pi' \in \classFP$
$\classFP \neq \classFNP \implies \forall \Pi \in \classFNPC: \Pi \notin \classFP$
$\Pi \in \classFNPC \iff \Pi \in \classFNP$ and $\exists \Pi' \in \classFNPC: \Pi' \leq \Pi$

Given a triangle subdivided in smaller triangles, a Sperner-coloring is
a vertex coloring in blue, red and yellow of the smaller triangles such that:

no vertex on the left side is blue
no vertex on the bottom side is red
no vertex on the top-right side yellow

Sperner
Input: a triangle with a Sperner-coloring
Output: a tri-colored small triangle

Thm. 2.26: $\SPERNER \in \classPPAD$

$\eps$Brouwer
Input: map $f: \Delta \to \Delta$, Lipschitz-constant $L \in \IRnn$,
Input: approximation bound $\eps \gt 0$
Output: approximate fix point $x \in \Delta$, i.e., $\norm{f(x) - x}_\infty \leq \eps$
Output: or Lipschitz-violating $x,y \in \Delta$, i.e., $\norm{f(x)-f(y)}_\infty \gt L\norm{x-y}_\infty$

Thm. 2.27: $\epsBROUWER \leq \SPERNER$ (hence, $\epsBROUWER \in \classPPAD$)

Fact 2.28: Both $\epsBROUWER$ and $\SPERNER$ are PPAD-complete (also for higher dimensions)